package com.jack.leetcode.string;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by zhang_j on 2020/7/23
 */
public class 串联所有单词的子串 {

    public static void main(String[] args) {
        String[] words = {"word","good","best","word"};
        findSubstring("wordgoodwordgoodbestword", words);
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        int m = words.length;
        if(m == 0){
            return new ArrayList<>();
        }
        Map<String, Integer> sNumberMap = new HashMap<>();
        for (String word : words) {
            Integer num = sNumberMap.getOrDefault(word, 0);
            sNumberMap.put(word, num+1);
        }
        List<Integer> result = new ArrayList<>();
        int oneWordLen = words[0].length();
        for(int i = 0;i < s.length() - oneWordLen * m + 1;i++){
            String tmp = s.substring(i, i + oneWordLen * m);
            int index = 0;
            Map<String, Integer> newMap = new HashMap<>(sNumberMap);
            boolean tmpResult = false;
            while(index < oneWordLen * m){
                String sub = tmp.substring(index, index + oneWordLen);
                if(!newMap.containsKey(sub) || newMap.get(sub) <= 0){
                    break;
                }
                newMap.put(sub, newMap.get(sub)-1);
                index += oneWordLen;
                if(index >= oneWordLen*m){
                    tmpResult = true;
                }
            }
            if(tmpResult){
                result.add(i);
            }
        }
        return result;
    }
}
